Search results for "knapsack problem"
showing 10 items of 16 documents
A decomposition approach for multidimensional knapsacks with family-split penalties
2022
The optimization of Multidimensional Knapsacks with Family-Split Penalties has been introduced in the literature as a variant of the more classical Multidimensional Knapsack and Multi-Knapsack problems. This problem deals with a set of items partitioned in families, and when a single item is picked to maximize the utility, then all items in its family must be picked. Items from the same family can be assigned to different knapsacks, and in this situation split penalties are paid. This problem arises in real applications in various fields. This paper proposes a new exact and fast algorithm based on a specific Combinatorial Benders Cuts scheme. An extensive experimental campaign computational…
Cryptanalysis of Knapsack Cipher Using Ant Colony Optimization
2018
Ant Colony Optimization is a search metaheuristic inspired by the behavior of real ant colonies and shown their effectiveness, robustness to solve a wide variety of complex problems. In this paper, we present a novel Ant Colony Optimization (ACO) based attack for cryptanalysis of knapsack cipher algorithm. A Cipher-text only attack is used to discover the plaintext from the cipher-text. Moreover, our approach allows us to break knapsack cryptosystem in a minimum search space when compared with other techniques. Experimental results prove that ACO can be used as an effective tool to attack knapsack cipher.
Learning Automata-Based Solutions to Stochastic Nonlinear Resource Allocation Problems
2009
“Computational Intelligence” is an extremely wide-ranging and all-encompassing area. However, it is fair to say that the strength of a system that possesses “Computational Intelligence” can be quantified by its ability to solve problems that are intrinsically hard. One such class of NP-Hard problems concerns the so-called family of Knapsack Problems, and in this Chapter, we shall explain how a sub-field of Artificial Intelligence, namely that which involves “Learning Automata”, can be used to produce fast and accurate solutions to “difficult” and randomized versions of the Knapsack problem (KP).
A genetic algorithm for the minimum generating set problem
2016
Graphical abstractDisplay Omitted HighlightsWe propose a novel formulation for the MGS problem based on multiple knapsack.The so-conceived MGS problem is solved by a novel GA.The GA embeds an intelligent construction method and specialized crossover operators.We perform a thorough comparison with regards to state-of-the-art algorithms.The proposal proves to be very competitive, specially for large and hard instances. Given a set of positive integers S, the minimum generating set problem consists in finding a set of positive integers T with a minimum cardinality such that every element of S can be expressed as the sum of a subset of elements in T. It constitutes a natural problem in combinat…
Learning automata-based solutions to the optimal web polling problem modelled as a nonlinear fractional knapsack problem
2011
We consider the problem of polling web pages as a strategy for monitoring the world wide web. The problem consists of repeatedly polling a selection of web pages so that changes that occur over time are detected. In particular, we consider the case where we are constrained to poll a maximum number of web pages per unit of time, and this constraint is typically dictated by the governing communication bandwidth, and by the speed limitations associated with the processing. Since only a fraction of the web pages can be polled within a given unit of time, the issue at stake is one of determining which web pages are to be polled, and we attempt to do it in a manner that maximizes the number of ch…
GRASP with path relinking for the orienteering problem
2014
In this paper, we address an optimization problem resulting from the combination of the well-known travelling salesman and knapsack problems. In particular, we target the orienteering problem, originated in the context of sport, which consists of maximizing the total score associated with the vertices visited in a path within the available time. The problem, also known as the selective travelling salesman problem, is NP-hard and can be formulated as an integer linear program. Since the 1980s, several solution methods for this problem have been developed and applied to a variety of fields, particularly in routing and tourism. We propose a heuristic method—based on the Greedy Randomized Adapt…
On Using a Hierarchy of Twofold Resource Allocation Automata to Solve Stochastic Nonlinear Resource Allocation Problems
2007
Recent trends in AI attempt to solve difficult NP-hard problems using intelligent techniques so as to obtain approximately-optimal solutions. In this paper, we consider a family of such problems which fall under the general umbrella of "knapsack-like" problems, and demonstrate how we can solve all of them fast and accurately using a hierarchy of Learning Automata (LA). In a multitude of real-world situations, resources must be allocated based on incomplete and noisy information, which often renders traditional resource allocation techniques ineffective. This paper addresses one such class of problems, namely, Stochastic Non-linear Fractional Knapsack Problems. We first present a completely …
Dynamic programming and Munkres algorithm for optimal photovoltaic arrays reconfiguration
2015
Abstract In this paper, an original formulation of the control problem for optimal PV array reconfiguration, following a Total Cross Tied layout, is proposed. The formulation follows the well-known subset sum problem, which is a special case of the knapsack problem. The reconfiguration is a measure devoted to mitigate the mismatch effect and maximize the output power of small photovoltaic plants under non-homogeneous working conditions. Therefore, reconfiguration means changing the connections of the solar panels adaptively by a dynamic switching matrix. The control system implements an easy dynamic programming algorithm to change the switches layout. The use of the Munkres assignment metho…
Stabilized branch-and-price algorithms for vector packing problems
2018
Abstract This paper considers packing and cutting problems in which a packing/cutting pattern is constrained independently in two or more dimensions. Examples are restrictions with respect to weight, length, and value. We present branch-and-price algorithms to solve these vector packing problems (VPPs) exactly. The underlying column-generation procedure uses an extended master program that is stabilized by (deep) dual-optimal inequalities. While some inequalities are added to the master program right from the beginning (static version), other violated dual-optimal inequalities are added dynamically. The column-generation subproblem is a multidimensional knapsack problem, either binary, boun…
A Hierarchy of Twofold Resource Allocation Automata Supporting Optimal Sampling
2009
We consider the problem of allocating limited sampling resources in a "real-time" manner with the purpose of estimating multiple binomial proportions. More specifically, the user is presented with `n ' sets of data points, S 1 , S 2 , ..., S n , where the set S i has N i points drawn from two classes {*** 1 , *** 2 }. A random sample in set S i belongs to *** 1 with probability u i and to *** 2 with probability 1 *** u i , with {u i }. i = 1, 2, ...n , being the quantities to be learnt. The problem is both interesting and non-trivial because while both n and each N i are large, the number of samples that can be drawn is bounded by a constant, c . We solve the problem by first modelling it a…